package tester.utilities;

import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import tester.DependsOn;

/**
 * Class with a single static method, sortByDependencies.  This is a 
 * utility class that allows for us to sort test methods by their 
 * dependencies.  
 * @author w_jossey
 *
 */
public class DependencyArranger {

	/**
	 * Takes a list of methods and sorts them for execution purposes by order of their
	 * dependencies.  The sorting algorithm will work at O(n^2) in the worst case.
	 * @param methodList methods to be sorted
	 * @return the sorted list
	 */
	public synchronized static Collection<Method> sortByDependencies(
			Collection<Method> methodList) {

		/* The return list */
		ArrayList<Method> returnList = new ArrayList<Method>(methodList.size());
		
		/* We create a dependency list that will be two dimensional */
		ArrayList<ArrayList<Method>> dependencyList = new ArrayList<ArrayList<Method>>();
		
		/*We create a HashMap for quick lookup */
		HashMap<String, Integer> locationLookup = new HashMap<String, Integer>();

		/*We turn the old method list into a synchronized linked list so we can do quick removes */
		List<Method> oldList = Collections.synchronizedList(new LinkedList<Method>(methodList));

		/* First pass */
		Iterator<Method> iter = oldList.iterator();
		synchronized(oldList){
			do {
				Method curr;
				curr = iter.next();
				if (!curr.isAnnotationPresent(DependsOn.class)) {
					/*Make the current non-dependent method a root method */
					ArrayList<Method> temp = new ArrayList<Method>();
					temp.add(curr);
					dependencyList.add(temp);
					locationLookup.put(curr.getName(), dependencyList.size() - 1);
					iter.remove();
				}
				/*Iterate while there are still methods left to inspect */
			} while (iter.hasNext());

			if (dependencyList.isEmpty()) {
				/* Can only enter here if we have no non-dependent methods */
				throw new RuntimeException(
						"Must have at least one non-dependent method");
			}

			/* While we have at least one dependent method remaining */
			while (!oldList.isEmpty()) {
				/*Point the iterator to the head of the list */
				iter = oldList.iterator();
				do {
					Method curr;
					curr = iter.next();
					DependsOn annot = curr.getAnnotation(DependsOn.class);
					Integer loc = locationLookup.get(annot.value());
					if (loc != null) {
						/* If the loc != null, then our dependent method is
						 * already in the list.                            */
						ArrayList<Method> subList = dependencyList.get(loc);
						subList.add(curr);
						
						/*Store this method into the lookup hash */
						locationLookup.put(curr.getName(), loc);
						iter.remove();
					}
					/*Iterate over the remainder of the list */
				} while (iter.hasNext());
			}
		}

		/* Go through and construct the return list */
		for (ArrayList<Method> list : dependencyList) {
			returnList.addAll(list);
		}

		return returnList;

	}

}
